package gold.digger;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC488 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 未来需要再次复习此道题目
     * @return:
     */
    class Solution {
        int INF = 0x3f3f3f3f;
        String b;
        int m;
        Map<String, Integer> memo = new HashMap<>();

        public int findMinStep(String a, String _b) {
            b = _b;
            m = b.length();
            int ans = dfs(a, 1 << m);
            return ans == INF ? -1 : ans;
        }

        int dfs(String a, int cur) {
            if (a.length() == 0) return 0;
            if (memo.containsKey(a)) return memo.get(a);
            int res = INF;
            int n = a.length();

            for (int i = 0; i < m; i++) {
                if (((cur >> i) & 1) == 1) continue;
                int next = (1 << i) | cur;

                for (int j = 0; j <= n; j++) {
                    boolean ok = false;
                    if (j > 0 && j < n && a.charAt(j) == a.charAt(j - 1) && a.charAt(j - 1) != b.charAt(i)) ok = true;
                    if (j < n && a.charAt(j) == b.charAt(i)) ok = true;
                    if (!ok) continue;

                    StringBuilder sb = new StringBuilder();
                    sb.append(a.substring(0, j)).append(b.substring(i, i + 1));
                    if (j != n) sb.append(a.substring(j));
                    int k = j;
                    while (0 <= k && k < sb.length()) {
                        char c = sb.charAt(k);
                        int l = k, r = k;
                        while (l >= 0 && sb.charAt(l) == c) l--;
                        while (r < sb.length() && sb.charAt(r) == c) r++;
                        if (r - l - 1 >= 3) {
                            sb.delete(l + 1, r);
                            k = l >= 0 ? l : r;
                        } else {
                            break;
                        }
                    }
                    res = Math.min(res, dfs(sb.toString(), next) + 1);
                }
            }
            memo.put(a, res);
            return res;
        }
    }


    public void run() {
        Solution solution = new Solution();
        System.out.println(solution.findMinStep("WWRRBBWW", "WRBRW"));
    }

    public static void main(String[] args) throws Exception {
        LC488 an = new LC488();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
